/**********************************************************************************************/
/* FBL_BitSet.h																				  */
/*                                                                       					  */
/* Copyright Paradigma, 1993-2006                                        					  */
/* All Rights Reserved.                                                 					  */
/**********************************************************************************************/

#ifndef _FBL_BitSet_h
   #define _FBL_BitSet_h
#pragma once

#include <VShared/FBL/publ/Sets/FBL_Set.h>
#include <VShared/FBL/publ/Headers/FBL_pre_header.h>

 
/**********************************************************************************************/
FBL_Begin_Namespace


/**********************************************************************************************/
// Constants:

#define WORD_SIZE 		sizeof(int)
#define WORD_BITS_ON 	0xFFFFFFFF			// for sizeof(int) == 4


/**********************************************************************************************/
// forward declarations: 
SMART_CLASS( ArraySet );

SMART_CLASS( BitSet );
SMART_CLASS( BitSet_01 );
SMART_CLASS( BitSetIterator );
SMART_CLASS( BitSetIterator_01 );
SMART_ARRAY_OF_SMART_PTRS( ArrayOfBitsets, BitSet_Ptr );


/**********************************************************************************************/
//	General purpose class.
//	Implement Set of ulong numbers as BitSet.
//	On creation you must specify top value.
//
class FBL_SHARED_EXP_CLASS BitSet : public Set
{
		friend class ArraySet;
		friend class BitSetIterator;
		friend class BitSetIterator_01;

	protected://////////////////////////////////////////////////////////////////////////////////
							
							BitSet(){}			/// This constructor needs for inheritance.							
virtual		    			~BitSet( void );	/// This constructor needs for inheritance.


	public://///////////////////////////////////////////////////////////////////////////////////

		//-----------------
		// Construction:
		
							BitSet( ID_TYPE	inMaxValue );						
							BitSet( const BitSet& inSrc );
							BitSet( 
								ID_TYPE				inMaxValue,	 
								Const_ArraySet_Ptr	inSet );
						

	public://///////////////////////////////////////////////////////////////////////////////////

// Set API:
		
	//----------------------
	// Properties:

virtual ulong				get_Count( void ) const;
virtual SetIterator_Ptr		get_Iterator( void ) const;

virtual bool				get_IsEmpty	( void ) const throw();

	// ---------------------

virtual Set*				Clone( bool inCopy = true ) const throw();


	// ---------------------
	// Item methods:
		
virtual void				Append( ID_TYPE inItem );
virtual void				Remove( ID_TYPE inItem );
virtual bool				Include( ID_TYPE inItem ) const;					


	// ---------------------
	// Sorting Methods:
		
		bool				get_IsSorted( void ) const throw() { return true; }
		void				put_IsSorted( bool inSorted )  throw() 
								{ argused1( inSorted );	}
		
							/// Sort items by values.
		void				Sort( void ) throw() { /* do nothing. */ }


	//----------------------
	// Unary operators:

virtual Set_Ptr				Union 		 		( const Set_Ptr inSet ); // OR
virtual Set_Ptr				Intersection		( const Set_Ptr inSet ); // AND
virtual Set_Ptr				Difference   		( const Set_Ptr inSet ); // AND NOT
virtual Set_Ptr				SymmetricDifference	( const Set_Ptr inSet ); // XOR


	public://///////////////////////////////////////////////////////////////////////////////////

// I_Serializable API:

virtual void				From( I_IStream_Ptr inStream,
								  bool inBlock = true );

virtual void				From( I_PacketRcv*	 	inPacket,
								  bool 				inBlock = true );


virtual void				To( I_OStream_Ptr inStream,
								bool inBlock = true ) const;
							
virtual void				To( I_PacketSnd*	inPacket,
								bool 			inBlock = true ) const;
							
		
	public://///////////////////////////////////////////////////////////////////////////////////

// BitSet API:

	//----------------------
	// Properties:

		virtual uchar*		get_ArrayPtr	( void ) const;
		virtual ulong		get_BytesInArray( void ) const;
		

virtual ID_TYPE				get_Bits_1_Count( void ) const;
		ID_TYPE				get_Bits_0_Count( void ) const;

		ID_TYPE				get_MaxValue( void ) const;
		void				put_MaxValue( ID_TYPE inMaxValue );
		
							/// Returns first and last nonzero bytes in set (range 0..N-1).
virtual void				get_NonZeroBounds( 
								ID_TYPE& 	outFirst, 
								ID_TYPE& 	outLast ) const;
																	
		ulong				get_Size( void ) const { return mBytesInArray; }

	//---------------------
	// Set operations:

							/// Copy bytes from a given Set.
virtual void				operator= ( const BitSet& inSet );

							/// make this BitSet equal to specified bit set string.
virtual void				operator= ( const char* inBitString );

	
	//----------------------
	// Unary operators:
	
virtual bool				IsEqual( const BitSet& inSet ) const;
					
virtual void				Invert( void );	/// invert all bits.

		// The folowing methods execute operation in place.
		// Only BitSet have such methods. 
		//		
virtual void				Union 		 		( const BitSet& inSet ); // OR
virtual void				Intersection		( const BitSet& inSet ); // AND
virtual void				Difference   		( const BitSet& inSet ); // AND NOT
virtual void				SymmetricDifference	( const BitSet& inSet ); // XOR


	//----------------------
	// Binary operators. Create a new BitSet as result.
						
friend	FBL_SHARED_EXP 
		BitSet_Ptr			Union( 
								const BitSet& inSet1,
								const BitSet& inSet2 );
	
friend	FBL_SHARED_EXP 
		BitSet_Ptr			Intersection( 
								const BitSet& inSet1,
								const BitSet& inSet2 );
		
friend FBL_SHARED_EXP 
		BitSet_Ptr			Difference( 
								const BitSet& inSet1,
								const BitSet& inSet2 );
	

friend FBL_SHARED_EXP 
		BitSet_Ptr			SymmetricDifference( 
								const BitSet& inSet1,
								const BitSet& inSet2 );
	
	
	public://///////////////////////////////////////////////////////////////////////////////////
 
virtual bool 				FindContinuous(
								ulong		inCount,
								BitSet&		ioResult ) const;
		
virtual ID_TYPE 			FindNth_1_Bit( ulong inNth ) const;


	public://///////////////////////////////////////////////////////////////////////////////////
 
	//----------------------
	// Bit methods:


							/// Set all bits in set to 1/0.
virtual void				ClearAll( void );
virtual void				SetAll( void );
							
							/// Fill all bits in mArray starting from inStartValue by inItem.
virtual void				SetBits  ( 
								ID_TYPE inLeft	= 1, 
								ID_TYPE inRight = (ID_TYPE) -1 );

virtual void				ClearBits( 
								ID_TYPE inLeft	= 1, 
								ID_TYPE inRight = (ID_TYPE) -1 );

							/// Fill all bytes in mArray with given BYTE value.
virtual void				SetAllBytes( 
								uchar	inFillValue, 
								ID_TYPE inStartByte = 0 );
								

	protected://////////////////////////////////////////////////////////////////////////////////

				 ulong 		FindContinuous_Core(
								ulong		inCount,
								BitSet&		ioResult );

virtual void 				InitSelf( ID_TYPE inMaxValue );
							
							/// Calculate byte in mArray which contains bit of inItem.
		ulong				Loc( ID_TYPE inItem ) const;
							
							/// Returns Mask. &7 - means cutting of low 3 bits from value.
		uchar				Mask( ID_TYPE inItem ) const;
								

	protected://////////////////////////////////////////////////////////////////////////////////

		uchar*  			mArray;
		ulong				mBytesInArray;	// alligned to int.
							
		ID_TYPE				mMaxValue;
							
static 	uchar     			sMasks[8];
static	ulong 				sBitsCount[256];

};


/**********************************************************************************************/
inline bool BitSet::Include( ulong inItem ) const
{
	if( inItem && inItem <= mMaxValue )
	{
		--inItem;	// make inItem zero based.
		return bool( (mArray[ Loc(inItem) ] & Mask(inItem) ) != 0 );
	}	
	
	return false;	
}

/**********************************************************************************************/
inline void BitSet::Append( ulong inItem )
{
	if( inItem && inItem <= mMaxValue )
	{
		inItem--;	// make inItem zero based.
		mArray[ Loc( inItem ) ] |= Mask( inItem );
	}	
}

/**********************************************************************************************/
inline void BitSet::Remove( ulong inItem )
{
	if( inItem && inItem <= mMaxValue )
	{
		inItem--;
		mArray[ Loc( inItem ) ] &= (uchar) ~Mask( inItem );
	}	
}

/**********************************************************************************************/
inline void BitSet::SetAllBytes( uchar inFillValue, ID_TYPE inStartByte )
{
	uchar* p1  = mArray + inStartByte;
	memset( p1, inFillValue, mBytesInArray - inStartByte );				
	     
}


/**********************************************************************************************/
// General purpose class.
// Implements Set of ulong numbers as BitSet that have ONLY 1 or 0 bits.
// For such bitset we do NOT allocate array of N bits. 
// Instead we override methods so they always return value 1 or 0 for any bit.
// We get practically ZERO memory overhead for ANY size if bitset.
//
class FBL_SHARED_EXP_CLASS BitSet_01 : public BitSet
{
		friend class BitSetIterator_01;

	public://///////////////////////////////////////////////////////////////////////////////////

	//----------------------
	// Constructors:
		
							BitSet_01(
								bool	inType,			// type of bitset, true - filled 1, false - filled 0.
								ID_TYPE	inMaxValue );

							BitSet_01( const BitSet& inSrc );

							BitSet_01( 
								bool			inType,	// type of bitset, true - filled 1, false - filled 0.
								const BitSet&	inSrc );
						
virtual						~BitSet_01( void ){};


	public://///////////////////////////////////////////////////////////////////////////////////

// Set API:
		
	//----------------------
	// Properties:
		
virtual SetIterator_Ptr		get_Iterator( void ) const;
virtual bool				get_IsEmpty( void ) const throw();

	// ---------------------
	// Item methods:
		
virtual void				Append 	( ID_TYPE inItem );
virtual void				Remove	( ID_TYPE inItem );
virtual bool				Include( ID_TYPE inItem ) const;


	public://///////////////////////////////////////////////////////////////////////////////////

// BitSet API:
		
virtual uchar*				get_ArrayPtr( void ) const;
virtual ID_TYPE				get_Bits_1_Count( void ) const;

virtual void				get_NonZeroBounds( 
								ID_TYPE& 	outFirst, 
								ID_TYPE& 	outLast ) const;
		


	//----------------------
	// Set operations:

							/// Copy bytes from a given Set.
virtual void				operator= ( const BitSet& inSet );
									
							/// make this BitSet equal to specified bit set string.
virtual void				operator= ( const char* inBitString );
	
		
	//----------------------
	// Unary operators. Modify this set.
	
virtual bool				IsEqual( const BitSet& inSet ) const;
						
virtual void				Invert( void );
	
virtual void				Union 				( const BitSet& inSet );
virtual void				Intersection		( const BitSet& inSet );
virtual void				Difference   		( const BitSet& inSet );
virtual void				SymmetricDifference	( const BitSet& inSet );

	
	public://///////////////////////////////////////////////////////////////////////////////////
 
virtual ID_TYPE 			FindNth_1_Bit( ulong inNth ) const;

							// Set all bits in set to 1/0.
virtual void				ClearAll( void );
virtual void				SetAll	( void );
							
							// Fill all bits in mArray starting from inStartValue by inItem.
virtual void				SetBits  ( 
								ID_TYPE inLeft	= 1, 
								ID_TYPE inRight	= (ID_TYPE) -1 );
								
virtual void				ClearBits( 
								ID_TYPE inLeft	= 1, 
								ID_TYPE inRight = (ID_TYPE) -1 );

							// Fill all bytes in mArray with given BYTE value.
virtual void				SetAllBytes( 
								uchar inFillValue, 
								ID_TYPE inStartByte = 0 );
								

	protected://////////////////////////////////////////////////////////////////////////////////

virtual void 				InitSelf( ID_TYPE inMaxValue );


	private:////////////////////////////////////////////////////////////////////////////////////

		bool				mType;	 // true - bitset filled 1, false - 0.
};


/**********************************************************************************************/
FBL_End_Namespace

#include <VShared/FBL/publ/Headers/FBL_post_header.h>

#endif // _FBL_BitSet_h
